import java.util.*;


class Student {
    public int age;
    public String name;

    public Student(int age, String name) {
        this.age = age;
        this.name = name;
    }

    @Override
    public String toString() {
        return "Student{" +
                "age=" + age +
                ", name='" + name + '\'' +
                '}';
    }
}

class Imp implements Comparator<Integer> {
    @Override
    public int compare(Integer o1, Integer o2) {
        //小根堆
        //return o1.compareTo(o2);
        //大根堆
        return o2.compareTo(o1);
    }
}

class Imp2 implements Comparator<Student> {
    @Override
    public int compare(Student o1, Student o2) {
        //return o2.name.compareTo(o1.name);
        return o1.name.compareTo(o2.name);
    }
}

public class Test {
    public static void main(String[] args) {
        int[] array = new int[]{27, 15, 19, 18, 28, 34, 65, 49, 25, 37};
        TestHeap testHeap = new TestHeap();
        //初始化堆
        testHeap.initElem(array);
        //创建堆 向下调整，大根堆
        testHeap.createHeap();//O(N)
        //排序
        testHeap.heapSort();//O(N*logN)
        System.out.println("==========");
    }




    public static void main6(String[] args) {
        int[] array = new int[]{27, 15, 19, 18, 28, 34, 65, 49, 25, 37};
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(array.length, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2.compareTo(o1);
            }
        });
        //建立大根堆
        for (int i = 0; i < array.length; i++) {
            priorityQueue.offer(array[i]);
        }

        int size = array.length;
        int[] ret = new int[size];
        //交换排序
        while (priorityQueue.size() > 0) {
            ret[size - 1] = priorityQueue.poll();
            size--;
        }
        System.out.println(Arrays.toString(ret));
    }


    //求前k个最小元素
    public int[] smallestK(int[] arr, int k) {
        int[] ret = new int[k];
        if (arr == null || k == 0) {
            return ret;
        }

        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2.compareTo(o1);
            }
        });
        //1. 建立大小为k的大根堆 O(K*logK)
        for (int i = 0; i < k; i++) {
            priorityQueue.offer(arr[i]);
        }

        //2. 遍历剩下的N-K个元素与堆顶元素比较，删除，插入
        //O(N-K)*logK
        for (int i = k; i < arr.length; i++) {
            if (arr[i] < priorityQueue.peek()) {
                priorityQueue.poll();
                priorityQueue.offer(arr[i]);
            }
        }

        //下面这个不能算topK的复杂度，这个地方是整理数据
        //K*logK
        for (int i = 0; i < k; i++) {
            ret[i] = priorityQueue.poll();
        }
        return ret;
    }


    public int[] smallestK2(int[] arr, int k) {
        int[] ret = new int[k];

        if (arr == null || k == 0) {
            return ret;
        }
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(arr.length);

        //通过插入建堆，默认小根堆
        //相当于以向上调整的方式 建立小根堆 O(N*logN)
        for (int i = 0; i < arr.length; i++) {
            priorityQueue.offer(arr[i]);
        }

        //删除堆顶元素k次 O(k*logN)
        //每删除一个元素，都要向下调整，只调整0下标为根节点这一颗树
        for (int i = 0; i < k; i++) {
            ret[i] = priorityQueue.poll();
        }
        return ret;
    }


    public static void main5(String[] args) {
        int[] arr = {4, 1, 9, 2, 8, 0, 7, 3, 6, 5};
        // 一般在创建优先级队列对象时，如果知道元素个数，建议就直接将底层容量给好
        // 否则在插入时需要不多的扩容
        // 扩容机制：开辟更大的空间，拷贝元素，这样效率会比较低
        PriorityQueue<Integer> q = new PriorityQueue<>(arr.length);
        for (int e : arr) {
            q.offer(e);
        }
        System.out.println(q.size()); // 打印优先级队列中有效元素个数
        System.out.println(q.peek()); // 获取优先级最高的元素

        // 从优先级队列中删除两个元素之后，再次获取优先级最高的元素
        q.poll();
        q.poll();
        System.out.println(q.size()); // 打印优先级队列中有效元素个数
        System.out.println(q.peek()); // 获取优先级最高的元素

        q.offer(0);
        System.out.println(q.peek()); // 获取优先级最高的元素

        // 将优先级队列中的有效元素删除掉，检测其是否为空
        q.clear();
        if (q.isEmpty()) {
            System.out.println("优先级队列已经为空!!!");
        } else {
            System.out.println("优先级队列不为空");
        }
    }


    public static void main4(String[] args) {
        Imp2 imp2 = new Imp2();
        PriorityQueue<Student> priorityQueue = new PriorityQueue<>(imp2);
        priorityQueue.offer(new Student(10, "zhangsan"));
        priorityQueue.offer(new Student(20, "lisi"));

        System.out.println("============");

    }


    public static void main3(String[] args) {
        Imp imp = new Imp();
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(imp);
        priorityQueue.offer(10);
        priorityQueue.offer(5);
        priorityQueue.offer(6);

        System.out.println("===============");
    }


    public static void main2(String[] args) {
        /*PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
        priorityQueue.offer(10);
        priorityQueue.offer(5);
        priorityQueue.offer(6);*/

        /*PriorityQueue<Student> priorityQueue2 = new PriorityQueue<>();
        priorityQueue2.offer(new Student(10,"zhangsan"));
        priorityQueue2.offer(new Student(20,"lisi"));*/


        /*PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
        priorityQueue.offer(null);

        PriorityQueue<Integer> priorityQueue2 = new PriorityQueue<>(0);
        priorityQueue2.offer(10);*/

        /*PriorityQueue<Integer> priorityQueue3 = new PriorityQueue<>(20);
        priorityQueue3.offer(10);
        priorityQueue3.offer(5);
        priorityQueue3.offer(6);*/

        List<Integer> list = new LinkedList<>();
        list.add(1);
        list.add(6);

        //小根堆
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(list);
        priorityQueue.offer(10);
        priorityQueue.offer(20);
        System.out.println(priorityQueue.poll());


        System.out.println("============");

    }

    public static void main1(String[] args) {
        TestHeap testHeap = new TestHeap();
        int[] array = new int[]{27, 15, 19, 18, 28, 34, 65, 49, 25, 37};
        testHeap.initElem(array);

        testHeap.createHeap();

        //testHeap.push(80);

        System.out.println(testHeap.pop());

        System.out.println("=========");

    }


}
